package com.gxc.string;

/**
 * 如果一个字符串为str，把字符串str前面任意的部分挪到后面形成的字符串叫作str的旋转词。
 * 比如str="12345”，str的旋转词有"12345”、"23451”、"34512”、”45123”和”51234”。给定两个字符串a和b，请判断a和b是否互为旋转词。
 * 比如:
 * a="cdab"，b="abcd",返回true。
 * a="1ab2"，b="ab12"返回false。
 * a="2ab1"，b="ab12"，返回true。
 *
 * 解法：
 * 把两个a拼接在一起，看是否包含b，
 * 如果包含则返回true，否则false
 * kmp加速
 */
public class Rotate {

    public static void main(String[] args) {
        String a = "cdab";
        String b = "abcd";
        System.out.println(isRotate(a, b));

        a = "1ab2";
        b = "ab12";
        System.out.println(isRotate(a, b));

        a = "2ab1";
        b = "ab12";
        System.out.println(isRotate(a, b));
    }

    private static boolean isRotate(String a, String b) {
        if (a.length() != b.length()) return false;

        String aa = a+a;
        return isContain(aa, b);
    }

    /**
     * 字符串包含问题
     * kmp
     * @param aa
     * @param b
     * @return
     */
    private static boolean isContain(String aa, String b) {
        char[] bchars = b.toCharArray();
        int[] kmpnext = kmpnext(bchars);
        char[] achars = aa.toCharArray();
        int length = achars.length;
        //aa 字符串中当前的位置
        int acur = 0;
        //b 字符串中当前的位置
        int bcur = 0;
        while (acur<length && bcur<bchars.length) {
            if (achars[acur] == bchars[bcur]) {
                acur++;
                bcur++;
                //next 初始位置默认 -1
            } else if (kmpnext[bcur]>-1) {
                bcur = kmpnext[bcur];
            } else {
                acur++;
            }
        }
        return bcur==bchars.length?true:false;
    }

    /**
     * 查找字符串的辅助数组(等于最长公共前后缀右移一位，第一位补充-1)
     * @param chars
     * @return
     */
    private static int[] kmpnext(char[] chars) {
        int length = chars.length;
        int[] next = new int[length];
        //next 初始位置默认 -1
        next[0] = -1;
        //当前位置
        int cur = 1;
        //比较的位置
        int cm = 0;
        //当前位置到最后一位终止
        while (cur < length) {
            if (chars[cur] == chars[cm]) {
                next[++cur] = ++cm;
            } else if (cm>0){
                cm = next[cm];
            } else {
                next[cur]=0;
                cur++;
            }
        }
        return next;
    }
}
